Practical decision-making for graph structures
- For sparse graphs with many neighbor iteration operations, use an adjacency list. Sparse graphs (where m << n²) waste space with matrices since most entries are zero, while adjacency lists store only actual edges and provide O(deg(v)) neighbor access.
- For dense graphs with frequent adjacency tests, use an adjacency matrix. When you need to quickly check "does edge (u,v) exist?" repeatedly, the O(1) constant-time lookup of matrices outweighs their O(n²) space cost, especially when m ≈ n².
- For file interchange or simple storage, use an edge list. This representation is the most human-readable and easiest to parse, making it ideal for input/output operations, debugging, and data transfer between different systems or programs.
- Rule of thumb: Start with an adjacency list using hash sets for O(1) expected adjacency tests unless you have a specific reason to choose otherwise. This provides good all-around performance, handles sparse graphs well, and can be easily adapted if requirements change during development.